use std::clone;

use itertools::Update;

// 传统dfs遍历算法

// 图dfs相关
// https://leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-100-liked
// 200. 岛屿数量
// TIP: 经典dfs bfs算法题
pub fn num_islands(mut grid: Vec<Vec<char>>) -> i32 {
    enum ACT {
        UP,
        LEFT,
        RIGHT,
        DOWN,
    }

    fn next_pos(limit: (usize, usize), x: usize, y: usize, act: ACT) -> Option<(usize, usize)> {
        match act {
            ACT::UP => {
                if x > 0 {
                    return Some((x - 1, y));
                }
            }
            ACT::DOWN => {
                if limit.0 > x {
                    return Some((x + 1, y));
                }
            }
            ACT::LEFT => {
                if y > 0 {
                    return Some((x, y - 1));
                }
            }
            ACT::RIGHT => {
                if limit.1 > y {
                    return Some((x, y + 1));
                }
            }
        }
        None
    }

    fn cal_fill_size(grid: &mut Vec<Vec<char>>, pos: Option<(usize, usize)>) -> i32 {
        let limit: (usize, usize) = (grid.len() - 1, grid[0].len() - 1);
        match pos {
            Some((x, y)) => {
                if grid[x][y] != '1' {
                    return 0;
                }
                grid[x][y] = '2';
                return 1
                    + cal_fill_size(grid, next_pos(limit, x, y, ACT::UP))
                    + cal_fill_size(grid, next_pos(limit, x, y, ACT::DOWN))
                    + cal_fill_size(grid, next_pos(limit, x, y, ACT::LEFT))
                    + cal_fill_size(grid, next_pos(limit, x, y, ACT::RIGHT));
            }
            None => 0,
        }
    }

    let limit: (usize, usize) = (grid.len(), grid[0].len());

    // 采用dfs遍历(递归)
    (0..limit.0)
        .into_iter()
        .map(|i| {
            (0..limit.1)
                .into_iter()
                .map(|j| {
                    if cal_fill_size(&mut grid, Some((i, j))) > 0 {
                        1
                    } else {
                        0
                    }
                })
                .sum::<i32>()
        })
        .sum()
}

#[test]
pub fn test_num_islands() {
    let mut intro = vec![
        vec!['0', '1', '1', '0', '0'],
        vec!['1', '1', '1', '1', '0'],
        vec!['0', '0', '0', '0', '1'],
        vec!['1', '0', '0', '0', '0'],
        vec!['0', '1', '0', '0', '0'],
    ];

    println!("{}", num_islands(intro));
}

// 图dfs相关
// https://leetcode.cn/problems/rotting-oranges/?envType=study-plan-v2&envId=top-100-liked
// 994. 腐烂的橘子
// TIP: 经典dfs bfs算法题
pub fn oranges_rotting(mut grid: Vec<Vec<i32>>) -> i32 {
    #[derive(Clone, Copy)]
    enum ACT {
        UP,
        LEFT,
        RIGHT,
        DOWN,
    }

    fn next_pos(limit: (usize, usize), x: usize, y: usize, act: ACT) -> Option<(usize, usize)> {
        match act {
            ACT::UP => {
                if x > 0 {
                    return Some((x - 1, y));
                }
            }
            ACT::DOWN => {
                if limit.0 > x {
                    return Some((x + 1, y));
                }
            }
            ACT::LEFT => {
                if y > 0 {
                    return Some((x, y - 1));
                }
            }
            ACT::RIGHT => {
                if limit.1 > y {
                    return Some((x, y + 1));
                }
            }
        }
        None
    }

    let mut save_cnt = 0;
    let mut time = 0;
    // use std::collections::HashSet;
    let mut next_loop_stk = vec![];
    for x in (0..grid.len()) {
        for y in (0..grid[x].len()) {
            if grid[x][y] == 1 {
                save_cnt += 1;
            }
            if grid[x][y] == 2 {
                next_loop_stk.push((x, y));
            }
        }
    }
    if save_cnt == 0 {return 0;}
    let enum_vec = vec![ACT::UP, ACT::DOWN, ACT::LEFT, ACT::RIGHT];
    let limit: (usize, usize) = (grid.len() - 1, grid[0].len() - 1);
    while !next_loop_stk.is_empty()  {
        for n in (0..next_loop_stk.len()) {
            if let Some((x, y)) = next_loop_stk.pop() {
                for act in enum_vec.iter() {
                    match next_pos(limit, x, y, *act) {
                        Some((x, y)) => {
                            if grid[x][y] == 1 {
                                grid[x][y] = 2;
                                save_cnt-=1;
                                next_loop_stk.insert(0,(x, y));
                            }
                        }
                        None => {}
                    }
                }
            }
        }
        time += 1;
    }
    if save_cnt==0{
        time
    }else {
        -1
    }
}

#[test]
pub fn test_oranges_rotting() {
    let mut intro = vec![vec![2, 1, 1], vec![0, 1, 1], vec![1, 1, 1]];

    println!("{}", oranges_rotting(intro));
}
